package likou.jindian;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/12/12 08:01
 */
public class _04_08 {
    static Deque<TreeNode> deque1 = new LinkedList();
    static Deque<TreeNode> deque2 = new LinkedList();

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(5);
//        root.right = new TreeNode(1);
//        root.left.left=new TreeNode(6);
//        root.left.right = new TreeNode(2);
//        root.left.right.left = new TreeNode(7);
//        root.left.right.right = new TreeNode(4);
//        root.right.left = new TreeNode(0);
//        root.right.right = new TreeNode(8);
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        System.out.println(lowestCommonAncestor(root,new TreeNode(1),new TreeNode(2)).val);
    }
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //记录当前层数,父节点的个数
        //记录当前的所有父节点
        //找到就开始往上找
        Deque<TreeNode> deque = new LinkedList();
        search(root, deque, p, q);

        int length = Math.min(deque1.size(), deque2.size());
        while (deque1.size() > length) {
            deque1.pollLast();
        }
        while (deque2.size() > length) {
            deque2.pollLast();
        }
        while (deque1.peekLast() != deque2.peekLast()) {
            deque1.pollLast();
            deque2.pollLast();
        }

        return deque1.peekLast();
    }

    public static void search(TreeNode root, Deque<TreeNode> deque, TreeNode p, TreeNode q) {
        if (root == null) {
            return;
        }
        deque.offerLast(root);
        if (deque1.size()!=0 && deque2.size()!=0) {
            return;
        }
        if (p.val == root.val) {
            deque1 = new LinkedList<>(deque);
        }
        if (q.val == root.val) {
            deque2 =  new LinkedList<>(deque);
        }
        search(root.left,deque,p,q);
        search(root.right,deque,p,q);
        deque.pollLast();
    }
}